package baseclass.e_tree;


import utils.TreeNode;
import utils.TreeUtil;

import java.util.Stack;

/**
 判断是否是二叉搜索树：
 二叉搜索树：大的放左，小的放又。
 二叉搜索树的中序遍历一定是升序的。所以只要在中序遍历的时候，拿出当前节点的值和上一个节点的值比较即可。
 用递归的方式比较麻烦，所以用遍历的方式，把之前的sout改为与上一次的节点值比较即可。

 注意，一般BST中不会有重复的值，即使有，也会放在同一个节点，让该节点的计数值++即可。
 */
public class Code07_IsBST  {

    //中序遍历。对节点一直往左滑下去，直到没有左孩子则pop，对pop的节点重复上述操作
    public static boolean isBST(TreeNode head){
        if(head == null)
            return true;
        Stack<TreeNode> stack = new Stack<>();
        int pre = Integer.MIN_VALUE;
        while (!stack.isEmpty() || head != null){
            if(head != null){
                stack.push(head);
                head = head.left;
            }else{
                //pop，然后给右孩子 ，重复上述过程
                head = stack.pop();
                //打印是中序遍历，这里拿出作比较即可。
                //System.out.println(head.value+" ");
                int cur = head.val;
                if(cur < pre){
                    return false;
                }
                pre = cur;
                head = head.right;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        TreeNode head = new TreeNode(4);
        head.left = new TreeNode(2);
        head.right = new TreeNode(6);
        head.left.left = new TreeNode(1);
        head.left.right = new TreeNode(3);
        head.right.left = new TreeNode(5);
//        head.right.right = new TreeNode(5);

        TreeUtil.printTree(head);
        System.out.println(isBST(head));
//        System.out.println(isCBT(head));

    }
}
